package src.java.medium;

public class Solution53 {
    public static int maxSubArray(int[] nums) {
        int prev = 0;
        int max = nums[0];
        for (int num : nums) {
            prev = Math.max(num, prev + num);
            max = Math.max(max, prev);
        }
        return max;
    }
//
//    public static int maxSubArray(int[] nums) {
//        int prev = 0;
//        int max = nums[0];
//        for (int num : nums) {
//            if (prev > 0) {
//                prev += num;
//            } else {
//                prev = num;
//            }
//            max = Math.max(max, prev);
//        }
//        return max;
//    }

    public static void main(String[] args) {
        int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(arr));
    }
}
